// https://www.lintcode.com/problem/longest-substring-without-repeating-characters/description
// https://leetcode.cn/problems/longest-substring-without-repeating-characters/

// 384. 最长无重复字符的子串
// 给定一个字符串，请找出其中无重复字符的最长子字符串。

// 样例
// 例如，在"abcabcbb"中，其无重复字符的最长子字符串是"abc"，其长度为 3。

// 对于，"bbbbb"，其无重复字符的最长子字符串为"b"，长度为1。

// 挑战
// O(n) 时间



class Solution {
public:
    /**
     * @param s: a string
     * @return: an integer
     */
    
    // 注意两种方法的区别，第一种用了滑动窗口。

    // 法一：两个指针，滑动窗口
    // • Hash + 双指针
    // • 类似sliding window 一边增加 一边减少
    int lengthOfLongestSubstring(string &s) {
        int j = 0;
        int record[256];
        memset(record, 0, sizeof(record));
        int ans = 0;
        for (int i = 0; i < s.length(); i++)
        {
            while (j < s.length() && record[s[j]] == 0)
            {
                record[s[j]] = 1;
                j++;
            }
            ans = max(ans, j - i);
            record[s[i]] = 0;
        }
        return ans;
    }

    // 法二：每个位置记录它到前一个相同字符(如有)的长度
    // O(n) 时间
    int lengthOfLongestSubstring(string &s) {
        int last[256]; 
        memset(last, -1, sizeof(last)); //初始化为-1
        int ans = 0, left = 0, len = s.length();
        for (int i = 0; i < len; i++)
        {
            // if (last[s[i]] > left
            if (last[s[i]] >= left)
            {
                left = last[s[i]] + 1; // 直接更新left，因为子串重复就会导致重复
            }
            last[s[i]] = i;
            ans = max(ans, i - left + 1);
        }
        return ans;
    }
};